`
https://leetcode.cn/problems/remove-invalid-parentheses/
`

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function (s) {
  const res = []
  const track = []

  function backtrack(index, leftCount) {
    // 遍历到数组末尾，查看是否符合答案
    if (index === s.length) {
      const str = track.join('')
      if (isValid(str)) {
        res.push(str)
      }
      return
    }

    const c = s[index]
    // 如果遇到的不是括号，正常遍历
    if (c !== '(' && c !== ')') {
      track.push(c)
      backtrack(index + 1, leftCount)
      track.pop()
    } else {
      // 遇到括号，选择留或不留（即删或不删）
      // 新增剪枝逻辑，仅当还有多余的左括可以和右括号抵消的情况下，才考虑保留当前括号
      if (leftCount > 0 || c !== ')') {
        // 做选择
        track.push(c)
        if (c === '(') {
          leftCount++
        } else {
          leftCount--
        }
        backtrack(index + 1, leftCount)
        // 撤销选择
        track.pop()
        if (c === '(') {
          leftCount--
        } else {
          leftCount++
        }
      }

      backtrack(index + 1, leftCount)
    }
  }
  backtrack(0, 0)

  // 题目要的是删除最小数量的无效括号，所以还需要过滤掉数组里不是最长的
  let maxLen = 0
  for (const s of res) {
    maxLen = Math.max(maxLen, s.length)
  }
  const set = new Set()
  for (const s of res) {
    if (s.length === maxLen) {
      set.add(s)
    }
  }
  return Array.from(set)
};

function isValid(s) {
  let leftCount = 0
  for (const c of s) {
    if (c === '(') {
      leftCount++
    } else if (c === ')') {
      leftCount--
      if (leftCount < 0) return false
    }
  }
  return leftCount === 0
}